You are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]. Afterward, any entries that are less than or equal to their index are worth one point.
- For example, if we have
nums = [2,4,1,3,0], and we rotate byk = 2, it becomes[1,3,0,2,4]. This is worth3points because1 > 0[no points],3 > 1[no points],0 <= 2[one point],2 <= 3[one point],4 <= 4[one point].
Return the rotation indexkthat corresponds to the highest score we can achieve if we rotatednumsby it. If there are multiple answers, return the smallest such index k.
Input: nums = [2,3,1,4,0] Output: 3 Explanation: Scores for each k are listed below: k = 0, nums = [2,3,1,4,0], score 2 k = 1, nums = [3,1,4,0,2], score 3 k = 2, nums = [1,4,0,2,3], score 3 k = 3, nums = [4,0,2,3,1], score 4 k = 4, nums = [0,2,3,1,4], score 3 So we should choose k = 3, which has the highest score.
Input: nums = [1,3,0,2,4] Output: 0 Explanation: nums will always have 3 points no matter how it shifts. So we will choose the smallest k, which is 0.
1 <= nums.length <= 1050 <= nums[i] < nums.length
implSolution{pubfnbest_rotation(nums:Vec<i32>) -> i32{let n = nums.len();letmut prefix_sum = vec![0; n + 1];letmut max_score = 0;letmut ret = 0;for i in0..n { prefix_sum[(n + i - nums[i]asusize) % n] += 1; prefix_sum[i] -= 1;}for i in(0..n).rev(){ prefix_sum[i] += prefix_sum[i + 1];if max_score <= prefix_sum[i]{ max_score = prefix_sum[i]; ret = i;}} ret asi32}}